package com.datastructure.hashtable;

/**
 * @author: 临晖
 * @date: 2023/10/12
 * @description:
 */


import javax.lang.model.element.VariableElement;
import java.util.*;

/**
 * hash table
 */
public class Solution01 {

    /**
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        //首先判断长度是否相同，不相同的话，直接pass
        if (s.length() != t.length()) {
            return false;
        }


        int[] hash = new int[26];
        //for (int i = 0; i < hash.length; i++) {
        //    hash[i] = 0;
        //}

        for (int i = 0; i < t.length(); i++) {
            hash[s.charAt(i) - 'a']++;
            hash[t.charAt(i) - 'a']--;
        }

        for (int i = 0; i < hash.length; i++) {
            if (hash[i] != 0) {
                return false;
            }
        }
        return true;
    }


    /**
     *
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     * 如果可以，返回 true ；否则返回 false 。
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     *
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine.length() < ransomNote.length()) {
            return false;
        }

        int[] array = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            array[magazine.charAt(i) - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            array[ransomNote.charAt(i) - 'a']--;
            if (array[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }

        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0) {
                return false;
            }
        }
        return true;
    }


    /**
     *
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);         //排序
            String newStr = new String(charArray);
            List<String> val = map.getOrDefault(newStr, new ArrayList<String>());
            val.add(str);
            //重新存入
            map.put(newStr, val);
        }
        return new ArrayList<List<String>>(map.values());


    }


    /**
     *
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）
     *
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {

        //思路一
        //int lenP = p.length();
        //
        //int index1 = 0;
        //int index2 = lenP;
        //
        //ArrayList<Integer> list = new ArrayList<>();
        ////如果p得长度大于s得长度
        //if (lenP > s.length()) {
        //    return list;
        //}
        //
        //
        //char[] charArrayP = p.toCharArray();
        //Arrays.sort(charArrayP);
        //String strP = new String(charArrayP);
        //while(true) {
        //    String str = s.substring(index1, index2);
        //    char[] charArray = str.toCharArray();
        //    Arrays.sort(charArray);
        //    String newStr = new String(charArray);
        //    if (newStr.equals(strP)) {
        //        list.add(index1);
        //    }
        //
        //    index1++;
        //    index2++;
        //    //退出循环条件
        //    if (index2 > s.length()) {
        //        return list;
        //    }
        //}

        //思路二
        //表示出字符串s,和p的长度
        int lenS = s.length();
        int lenP = p.length();

        //定义hsahtable
        int[] arrayS = new int[26];
        int[] arrayP = new int[26];

        ArrayList<Integer> ans = new ArrayList<>();
        //第一次比较
        for (int i = 0; i < lenP; i++) {
            arrayS[s.charAt(i) - 'a']++;
            arrayP[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(arrayS, arrayP)) {
            ans.add(0);
        }

        //循环比较
        for (int i = 0; i < lenS - lenP; i++) {
            //将第一个字符去掉
            arrayS[s.charAt(i) - 'a']--;
            //添加第lenP个字符
            arrayS[s.charAt(i + lenP) - 'a']++;
            //以上俩步的意义就是，使得arrayS中始终维持lenP个字符，就像一个窗口序列一样，
            //以 1 的速断不断移动

            if (Arrays.equals(arrayS, arrayP)) {
                ans.add(i + 1);     //这里加一是因为，当i等于n时，我们将第n个字符移除，然后添加第n + lenP个字符，所以其实位置是 i + 1
            }
        }
        return ans;

    }

    public static void main(String[] args) {
        findAnagrams("cbaebabace", "abc");
    }
}
